package _动态规划系列._贪心之区间调度;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Author: 吕庆龙
 * @Date: 2020/4/2 19:43
 * <p>
 * 功能描述:
 */
public class Summary_0435 {

    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        return n - intervalSchedule(intervals);
    }

    public int intervalSchedule(int[][] intvs) {

        if (intvs.length == 0)
            return 0;

        Arrays.sort(intvs, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });
        int v_end = intvs[0][1];
        //
        int count = 1;

        for (int[] intv : intvs) {
            int v_start = intv[0];
            if (v_start >= v_end) { //找到下一个区间
                v_end = intv[1];
                count++;
            }
        }

        return count;
    }
}
